package company.tree;

import java.util.*;

/**
 * 113. 路径总和 II
 * 给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。
 * <p>
 * 叶子节点 是指没有子节点的节点。
 * 输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
 * 输出：[[5,4,11,2],[5,8,4,5]]
 * <p>
 * 输入：root = [1,2,3], targetSum = 5
 * 输出：[]
 * <p>
 * <p>
 * 输入：root = [1,2], targetSum = 0
 * 输出：[]
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/path-sum-ii
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class PathSumThree113 {
    static List<List<Integer>> ret = new LinkedList<List<Integer>>();
    static Map<TreeNode, TreeNode> map = new HashMap<TreeNode, TreeNode>();

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String[] input = sc.nextLine().split("\\s+");
        String[] node = input[0].replace("[", "").
                replace("]", "").replace("\\s+", "").split(",");
        input[1].replace("\\s+", "");
        TreeNode treeNode = null;
        treeNode = packTree(treeNode, node);
        System.out.println(pathSum(treeNode, Integer.parseInt(input[1])));
    }

    private static TreeNode packTree(TreeNode treeNode, String[] node) {
        // 根节点
        if (treeNode == null) {
            treeNode = new TreeNode(Integer.parseInt(node[0]));
        }
        Deque<TreeNode> deque = new LinkedList<>();
        deque.offer(treeNode);
        int idx = 0;
        int len = node.length;
        while (++idx < len) {
            // 取出父节点
            TreeNode poll = deque.poll();

            // 处理左子树
            if (poll.getLeft() == null) {
                if (!node[idx].equals("null")) {
                    TreeNode left = new TreeNode(Integer.parseInt(node[idx]));
                    poll.setLeft(left);
                    deque.offer(left);
                }
            }
            ++idx;

            // 处理右子树
            if (idx < len && poll.getRight() == null) {
                if (!node[idx].equals("null")) {
                    TreeNode right = new TreeNode(Integer.parseInt(node[idx]));
                    poll.setRight(right);
                    deque.offer(right);
                }
            }
        }
        return treeNode;
    }

    private static List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        List<List<Integer>> ret = new ArrayList<>();
        List<Integer> path = new ArrayList<>();
        if (root == null) {
            return ret;
        }
        dfs(root, ret, path, targetSum);
        return ret;
    }

    // 注意和TreeCommonAncestorTwo的bfs比较
    private static void dfs(TreeNode node, List<List<Integer>> ret, List<Integer> path, int targetSum) {
        if (node == null) {
            return;
        }
        path.add(node.getValue());
        if (node.getLeft() == null && node.getRight() == null) {
            if (path.stream().mapToInt(Integer::intValue).sum() == targetSum) {
                ret.add(new ArrayList<>(path));
            }
        }
        dfs(node.getLeft(), ret, path, targetSum);
        dfs(node.getRight(), ret, path, targetSum);

        // 当这个节点退出之后，才移除当前节点
        path.remove(path.size() - 1);
    }
}